from typing import List


class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        size1, size2 = len(nums1), len(nums2)

        left1, right1 = 0, size1  # nums1的左右边界
        left2, right2 = 0, size2  # nums2的左右边界

        need_num = (size1 + size2) // 2  # 中位数两侧各有多少值
        min_num, max_num = 0, 0  # 中位数左侧的值、中位数右侧的值

        while left1 < right1 and left2 < right2:
            mid1, mid2 = (left1 + right1) // 2, (left2 + right2) // 2

            mid1_left, mid1_right = mid1 - left1, right1 - mid1  # mid1左侧和右侧的元素数
            mid2_left, mid2_right = mid2 - left2, right2 - mid2  # mid2左侧和右侧的元素数

            break

        if left1 < right1:
            left1 += (need_num - min_num)

        if left2 < right2:
            left2 += (need_num - min_num)

        if (size1 + size2) % 2 == 0:
            return (nums2[left2 + (need_num - min_num)] + nums2[left2 + (need_num - min_num) + 1]) / 2
        else:
            return float(nums2[left2 + (need_num - min_num)])


if __name__ == "__main__":
    # print(Solution().findMedianSortedArrays(nums1=[1, 3], nums2=[2]))  # 2.0
    # print(Solution().findMedianSortedArrays(nums1=[1, 2], nums2=[3, 4]))  # 2.5
    # print(Solution().findMedianSortedArrays(nums1=[0, 0], nums2=[0, 0]))  # 0.0
    print(Solution().findMedianSortedArrays(nums1=[], nums2=[1]))  # 1.0
    print(Solution().findMedianSortedArrays(nums1=[2], nums2=[]))  # 2.0
